The present invention relates generally to data communication networks and more particularly relates to an apparatus for and a method of testing low level PNNI software in an ATM network.
Currently, there is a growing trend to make Asynchronous Transfer Mode (ATM) networking technology the base of future global communications. ATM has already been adopted as a standard for broadband communications by the International Telecommunications Union (ITU) and by the ATM Forum, a networking industry consortium.
ATM originated as a telecommunication concept defined by the Comite Consulatif International Telegraphique et Telephonique (CCITT), now known as the ITU, and the American National Standards Institute (ANSI) for carrying user traffic on any User to Network Interface (UNI) and to facilitate multimedia networking between high speed devices at multi-megabit data rates. ATM is a method for transferring network traffic, including voice, video and data, at high speed. Using this connection oriented switched networking technology centered around a switch, a great number of virtual connections can be supported by multiple applications through the same physical connection. The switching technology enables bandwidth to be dedicated for each application, overcoming the problems that exist in a shared media networking technology, like Ethernet, Token Ring and Fiber Distributed Data Interface (FDDI). ATM allows different types of physical layer technology to share the same higher layerxe2x80x94the ATM layer.
ATM uses very short, fixed length packets called cells. The first five bytes, called the header, of each cell contain the information necessary to deliver the cell to its destination. The cell header also provides the network with the ability to implement congestion control and traffic management mechanisms. The fixed length cells offer smaller and more predictable switching delays as cell switching is less complex than variable length packet switching and can be accomplished in hardware for many cells in parallel. The cell format also allows for multi-protocol transmissions. Since ATM is protocol transparent, the various protocols can be transported at the same time. With ATM, phone, fax, video, data and other information can be transported simultaneously.
ATM is a connection oriented transport service. To access the ATM network, a station requests a virtual circuit between it and other end stations, using the signaling protocol to the ATM switch. ATM provides the User Network Interface (UNI) which is typically used to interconnect an ATM user with an ATM switch that is managed as part of the same network.
The current standard solution for routing in a private ATM network is described in Private Network Node Interface (PNNI) Phase 0 and Phase 1 specifications published by ATM Forum. The previous Phase 0 draft specification is referred to as Interim Inter-Switch Signaling Protocol (IISP). The goal of the PNNI specifications is to provide customers of ATM network equipment some level of multi-vendor interoperability.
The Interim Local Management Interface (ILMI) for the PNNI protocol specification provides an auto-port configuration capability. This capability functions to minimize manual configuration operations for PNNI ports of switches. The Phase 0 solution to auto-port configuration is based on hop by hop routing utilizing a xe2x80x98best matchxe2x80x99 scheme. The Phase 1 PNNI based solution is based on Open Shortest Path First (OSPF) with the additions necessary for ATM. This scheme is essentially a xe2x80x98source routingxe2x80x99 scheme whereby each node has basic knowledge of the structure of the entire network and uses this knowledge to build a complete path from the source to the destination. When a connection is to be set up from a source to a destination, the source sends out a SETUP message that has within it the address of the destination. Each ATM network node along the way reads the next node from the SETUP message and forwards the message to an appropriate next node. This continues until the SETUP message arrives at its destination.
In the IISP Phase 0 specification standard, the ATM nodes in the network route the signaling SETUP message hop by hop (i.e., node by node) using a xe2x80x98best matchxe2x80x99 scheme. ATM addresses are 20 bytes long but only 19 bytes can be used for routing purposes. According to the IISP Phase 0 standard, several prefixes of the ATM address for each link can be registered.
When a node (i.e., an ATM switch) needs to decide to which particular node to route the received SETUP message to, it compares the destination address with all the registered addresses for all of its ports. Only if an address prefix is found that fully matches the destination address can the destination address be considered for routing. After all the prefixes are compared, the prefix address that is the longest is used to determine the routing of the SETUP message. It is important to note that the standard does not require the transfer of any routing information between two neighboring nodes. In addition, the standard also does not permit the use of a TRANSIT NET ID parameter during the signaling phase, which can be used to route to a different routing domain.
A disadvantage of this scheme is that all the prefixes of all neighboring nodes must be registered manually on each of the respective ports. For example, if a port is disconnected from a neighbor and connected to a new neighbor, then the registered addresses must be manually changed in both nodes. This type of network can be termed an absolutely static network.
As part of the ongoing enhancement to the ATM standard by work within the ATM Forum and other groups, the Private Network to Network Interface (PNNI) protocol Phase 1 has been developed for use between private ATM switches and between groups of private ATM switches. The PNNI specification includes two categories of protocols. The first protocol is defined for the distribution of topology information between switches and clusters of switches where the information is used to compute routing paths within the network. The main feature of the PNNI hierarchy mechanism is its ability to automatically configure itself within the networks in which the address structure reflects the topology. The PNNI topology and routing techniques are based on the well known link state routing technique.
The second protocol is effective for signaling, i.e., the message flows used to establish point-to-point and point-to-multipoint connections across the ATM network. This protocol is based on the ATM Forum User to Network Interface (UNI) signaling with mechanisms added to support source routing, crankback and alternate routing of source SETUP requests in the case of bad connections.
With reference to the PNNI Phase 1 specifications, the PNNI hierarchy begins at the lowest level where the lowest level nodes are organized into peer groups. A logical node in the context of the lowest hierarchy level is the lowest level node. A logical node is typically denoted as simply a node. A peer group is a collection of logical nodes wherein each node within the group exchanges information with the other members of the group such that all members maintain an identical view of the group. When a logical length becomes operational, the nodes attached to it initiate and exchange information via a well known Virtual Channel Connection (VCC) used as a PNNI Routing Control Channel (RCC).
Hello message are sent periodically by each node on this link. In this fashion the Hello protocol makes the two neighboring nodes known to each other. Each node exchanges Hello packets with its immediate neighbors to determine its neighbor""s local state information. The state information includes the identity and peer group membership of the node""s immediate neighbors and a status of its links to its neighbors. Each node then bundles its state information in one or more PNNI Topology State Elements (PTSEs) which are subsequently flooded throughout the peer group.
PTSEs are the smallest collection of PNNI routing information that is flooded as a unit among all logical nodes within a peer group. A node topology database consists of a collection of all PTSEs received, which represent that particular node""s present view of the PNNI routing topology. In particular, the topology database provides all the information required to compute a route from the given source node to any destination address reachable in or through that routing domain.
When neighboring nodes at either end of a logical length begin initializing through the exchange of Hellos, they may conclude that they are in the same peer group. If it is concluded that they are in the same peer group, they proceed to synchronize their topology databases. Database synchronization includes the exchange of information between neighboring nodes resulting in the two nodes having identical topology databases. A topology database includes detailed topology information about the peer group in which the logical node resides in addition to more abstract topology information representing the remainder of the PNNI routing domain.
During a topology database synchronization, the nodes in question first exchange PTSE header information, i.e., they advertise the presence of PTSEs in their respective topology databases. When a node receives PTSE header information that advertises a more recent PTSE version than the one that it has already or advertises a PTSE that it does not yet have, it requests the advertised PTSE and updates its topology database with the subsequently received PTSE. If the newly initialized node connects to a peer group then the ensuing database synchronization reduces to a one way topology database copy. A link is advertised by a PTSE transmission only after the database synchronization between the respective neighboring nodes has successfully completed. In this fashion, the link state parameters are distributed to all topology databases in the peer group.
Flooding is the mechanism used for advertising links whereby PTSEs are reliably propagated node by node throughout a peer group. Flooding ensures that all nodes in a peer group maintain identical topology databases. A short description of the flooding procedure follows. PTSEs are encapsulated within PNNI Topology State Packets (PTSPs) for transmission. When a PTSP is received its component PTSEs are examined. Each PTSE is acknowledged by encapsulating information from its PTSE header within the acknowledgment packet that is sent back to the sending neighbor. If the PTSE is new or of more recent origin then the node""s current copy, the PTSE is installed in the topology database and flooded to all neighboring nodes except the one from which the PTSE was received. A PTSE sent to a neighbor is periodically retransmitted until acknowledged.
Note that flooding is an ongoing activity wherein each node issues PTSPs with PTSEs that contain updated information. The PTSEs contain the topology databases and are subject to aging and get removed after a predefined duration if they are not refreshed by a new incoming PTSE. Only the node that originally originated a particular PTSE can re-originate that PTSE. PTSEs are reissued both periodically and on an event driven basis.
As described previously, when a node first learns about the existence of a neighboring peer node which resides in the same peer group, it initiates the database exchange process in order to synchronize its topology database with that of its neighbor""s. The database exchange process involves exchanging a sequence of database summary packets that contain the identifying information of all PTSEs in a node topology database. The database summary packet performs an exchange utilizing a lock step mechanism whereby one side sends a database summary packet and the other side responds with its own database summary packet, thus acknowledging the received packet.
When a node receives a database summary packet from its neighboring peer, it first examines its topology database for the presence of each PTSE described within the packet. If the particular PTSE is not found in its topology database or if the neighboring peer has a more recent version of the PTSE then the node requests the PTSE from the particular neighboring peer or optionally from another neighboring peer whose database summary indicates that it has the most recent version of the PFSE.
A corresponding neighboring peer data structure is maintained by the nodes located on either side of the link. The neighboring peer data structure includes information required to maintain database synchronization and flooding to neighboring peers.
It is assumed that both nodes on either side of the link begin in the Neighboring Peer Down state. This is the initial state of the neighboring peer for this particular state machine. This state indicates that there are no active links through the neighboring peer. In this state, there are no adjacencies associated with the neighboring peer either. When the link reaches the point in the Hello protocol where both nodes are able to communicate with each other, the event AddPort is triggered in the corresponding neighboring peer state machine. Similarly when a link falls out of communication with both nodes the event DropPort is triggered in the corresponding neighboring peering state machine. The database exchange process commences with the event AddPort that is thus triggered but only after the first link between the two neighboring peers is up. When the DropPort event for the last link between the neighboring peers occurs, the neighboring peer state machine will internally generate the DropPort last event closing all state information for the neighboring peers to be cleared.
It is while in the Negotiating state that the first step is taken in creating an adjacency between two neighboring peer nodes. During this step it is decided which node is the master, which is the slave and it is also in this state that an initial Database Summary (DS) sequence number is decided upon. Once the negotiation has been completed, the Exchanging state is entered. In this state the node describes is topology database to the neighboring peer by sending database summary packets to it.
After the peer processes the database summary packets, the missing or updated PTSEs can then be requested. In the Exchanging state the database summary packets contain summaries of the topology state information contained in the node""s database. In the case of logical group nodes, those portions of the topology database that where originated or received at the level of the logical group node or at higher levels are includes in the database summary. The PTSP and PTSE header information of each such PTSE is listed in one of the node""s database packets. PTSEs for which new instances are received after the exchanging status has been entered may not be included in any database summary packet since they will be handled by normal flooding procedures.
The incoming data base summary packet on the receive side is associated with a neighboring peer via the interface over which it was received. Each database summary packet has a database summary sequence number that is implicitly acknowledged. For each PTSE listed, the node looks up the PTSE in its database to see whether it also has an instance of that particular PTSE. If it does not or if the database copy is less recent, then the node either re-originates the newer instance of the PTSE or flushes the PTSE from the routing domain after installing it in the topology database with a remaining lifetime set accordingly.
Alternatively, if the listed PTSE has expired, the PTSP and PTSE header contents in the PTSE summary are accepted as a newer or updated PTSE with empty contents. If the PTSE is not found in the node""s topology database, the particular PTSE is put on the PTSE request list so it can be requested from a neighboring peer via one or more PTSE request packets.
If the PTSE request list from a node is empty, the database synchronization is considered complete and the node moves to the Full state.
However, if the PTSE request list is not empty then the Loading state is entered once the node""s last database summary packet has been sent but the PTSE request list is not empty. At this point, the node now knows which PTSE needs to be requested. The PTSE request list contains a list of those PTSEs that need to be obtained in order to synchronize that particular node""s topology database with the neighboring peer""s topology database. To request these PTSEs, the node sends the PTSE request packet that contains one or more entries from the PTSE request list. The PTSE request list packets are only sent during the Exchanging state and the Loading state. The node can send a PTSE request packet to a neighboring peer and optionally to any other neighboring peers that are also in either the Exchanging state or the Loading state and whose database summary indicates that they have the missing PTSEs.
Received PTSE request packets specify a list of PTSEs that the neighboring peer wishes to receive. For each PTSE specified in the PTSE request packet, its instance is looked up in the node""s topology database. The requested PTSEs are subsequently bundled into PTSPs and transmitted to the neighboring peer. Once the last PTSE and the PTSE request list have been received, the node moves from the Loading state to the Full state. Once the Full state has been reached, the node has received all PTSEs known to be available from its neighboring peer and links to the neighboring peer can now be advertised within PTSEs.
IISP is a method of routing and performing auto registration (auto configuration) in an ATM network. The method simplifies the configuration and routing for ATM networks having a relatively large number of nodes. Networks are constructed in hierarchical fashion in the form of branches and trees and assigned network address prefixes in accordance with their location in the network. Network nodes periodically exchange identification information permitting both switches on either side of a link to be aware of who they are connected to. Each node registers a network address and an associated significant length for each of its neighbors on each of its links. A node performs routing by comparing the destination address against each of its registered addresses for all its links. The routing method takes advantage of the network address prefix to ensure that the routing proceeds in the correct direction towards the destination and does not enter a tree or a branch that does not contain the destination. In addition, each node performs load balancing at each point in the routing process. A node can generate crankback messages if the routing leads to a dead end.
In the address prefix exchange method, each node discovers who its neighbors are. This is accomplished by each node sending out on all its NNI ports an identification message that comprises the address prefix assigned to it and its significant length. This message is sent out periodically (e.g., every second). The nodes that receive it compare the address prefix in the message to the special NNI type address that is registered on the port the message was received on. If the addresses do not match or there is no NNI address registered, then the node makes the received address prefix the new registered NNI address for that port and changes its routing tables accordingly. If the addresses do match, the message is ignored.
Sending out identification messages on a periodic basis enables a node to detect almost immediately if it becomes connected to a new neighbor. If a change is detected, the node""s modifies its routing tables accordingly. In addition, since each node address prefix is unique and is assigned in hierarchical fashion as described above, it is guaranteed that either the local address prefix (i.e., the address prefix of the node itself) or the remote node address prefix will be smaller.
The IISP signaling specification requires that one side of a link be designated as the USER and the other side as the NETWORK. In networks constructed in accordance with the present invention, on NNI links, if the significant length of the local prefix (i.e., of the node itself) is shorter than that of a neighbor, then the local side is set as the NETWORK. This particular link attribute setting allows the signaling to automatic align after a dynamic link replacement when a node""s neighbors are changed.
Thus, the automatic exchange of network address prefixes causes the routing tables of each node to be updated and permits the signaling to xe2x80x98come upxe2x80x99. This is in contrast to IISP Phase 0 which requires that link attributes be set manually. This method is thus especially advantageous in large networks consisting of more than two nodes.
As an alternative to the automatic exchange of network addresses, the transfer of addresses can be performed manually at each node or can be performed in accordance with ILMI registration procedures.
Note that the above described PNNI and IISP routing schemes are inherently different. In PNNI only full address matching is permitted, i.e., an address must fully match the address entry in the topology database. In contrast, IISP permits partial address matching. The IISP routing method is a partially static routing scheme.
In addition, there are many ATM switches currently in operation that support only the IISP type routing. It is desirable to permit the owners of many of these older ATM switches to upgrade their switches to the more modern PNNI type routing. Upgrades can be performed by upgrading the operating software within the switches. In order to permit upgraded nodes to operate in a PNNI network, the upgraded switches can only support a minimal PNNI configuration. This means that the hierarchical features of PNNI are not supported. More specifically, in a minimal subset of PNNI, a node cannot function as a border node or as a Peer Group Leader (PGL). A border node is a node that has a link to another peer group and executes a special finite state machine (FSM). The PGL is the node that represents the whole peer group and functions as the key component for building large hierarchical networks.
A conflict exists, however, since a major benefit of PNNI is its ability to permit network designers to construct large hierarchical networks. Using PNNI, networks can be constructed that comprise peer groups having from dozens to over a hundred nodes. The concept is that many nodes in the same peer group can be represented as one node in a higher level of the hierarchy. Since PNNI utilizes a link state, source routing type routing scheme wherein each node has a view of the entire network, it is the hierarchy that permits the division of the network view into smaller chunks. In PNNI, very large portions of the network comprising a large number of nodes may be viewed by nodes in other peer groups as a single logical node.
A diagram illustrating an example hierarchical PNNI ATM network having a two level hierarchy is shown in FIG. 1. The example network, generally referenced 10, comprises four peer groups 12 labeled A.1, A.2, A.3 and A.4. Within each peer group 12, are located one or more nodes 16. In each peer group one of the nodes has been elected Peer Group Leader (PGL) as is labeled in FIG. 1. The peer groups 12 are connected together via one or more links 18 connecting the border nodes 24 from each peer group on either side of the link. A logical peer group 14 labeled A has been created comprising four logical group nodes 22. One of the logical group nodes has been elected peer group leader as indicated in FIG. 1. The logical group nodes 22 are connected together via logical links 20. Although only two levels of the PNNI hierarchy are shown, the network 10 can be constructed having any number of nodes and levels.
Those skilled in the ATM network art are familiar with the Private Network to Network Interface (PNNI) routing protocol, an advanced routing protocol for use in current and future ATM networks. The latest PNNI specification is described in the ATM Forum standard xe2x80x9cPrivate Network to Network Interface Specification Version 1.0,xe2x80x9d March 1996 (PNNI 1.0). This protocol is a relatively complex protocol both from an implementation perspective as well as from a testing perspective. Most realizations of the PNNI protocol to date implement only the mandatory portion of the standard known as the xe2x80x9cMinimum Functionxe2x80x9d subset. The Minimum Function subset implements only the behavior of a xe2x80x9clowest Level Nodexe2x80x9d. Such a node can operate only in a single Peer Group and has the following restrictions:
1. Cannot function as a border node;
2. Cannot instantiate logical nodes;
3. Cannot be a peer group leader;
A difficulty arises in the case where a node with a Minimum Function PNNI implementation must operate correctly with other nodes in a hierarchical environment that have implemented the PNNI hierarchy. Since a Minimum Function node cannot function in a hierarchical environment, it becomes very difficult to test and debug such nodes to ensure their operation in environments where there are nodes that do implement the PNNI hierarchy.
The present invention is an apparatus for and method for enabling the debugging and testing of complex multilevel PNNI based ATM networks. The invention has applications in networks wherein one or more nodes implement only the Minimum Function PNNI implementation and wherein these nodes must operate correctly in a PNNI hierarchy environment. The method comprises injecting a plurality of PTSEs representing simulated virtual portions of an ATM network. Typically the PTSEs represent hierarchical portions of ATM networks that either could not be implemented or could be implemented but with great difficulty. The virtual portions of the networks may or may not have been able to be created using real physical network elements.
The method permits dynamic debugging of various network configurations and also permits testing such things as the validity of call routing decisions as well as checking implementation functionality in very large network environments. The method does not impose any practical limitations or restrictions on the number of hierarchical levels, the number of nodes in each level or the number of peer groups. In fact, the PTSE injection method of the present invention can be used to test the behavior of a node when an overload occurs in its database.
A major advantage of the method of the present invention is that compared to a full simulation testing process, the method provides for the system under test to execute the complete device software on a real physical device as opposed to a completely simulated network hosted by a computer platform. A fully simulated testing process, by definition, cannot accurately represent a real network system.
The invention comprises first generating the injection file containing all the PTSEs to be simulated and then injecting this file into the node under test. The injection file comprises an ASCII file containing repeating records consisting of the Originating Node ID, Peer Group ID and the body of the PTSE.
The injection process comprises reading the ASCII file, parsing the contents and constructing the topology database by processing the binary version of the contents using already existing PNNI processing routines in the switch.
There is provided in accordance with the present invention, in a Private Network to Network Interface (PNNI) based Asynchronous Transfer Mode (ATM) network, a method of simulating a virtual ATM network coupled to a real portion consisting of a plurality of real nodes, the method comprising the steps of generating a plurality of PNNI Topology State Elements (PTSEs) representing a combination of network elements that function to form the virtual network and injecting the plurality of PTSEs into one of the real nodes designated the node under test, the node under test being part of a real portion of the ATM network which, in combination with the virtual portion, make up the ATM network being tested.
The step of generating comprises the steps of preparing the plurality of PTSEs representing a network configuration corresponding to the virtual network to be simulated and creating an injection output file from the plurality of PTSEs.
The injection output file comprises American Standard Code for Information Interchange (ASCII) characters and comprises repeating records consisting of Originating Node ID, Peer Group ID and PTSE body.
The step of generating comprises the steps of preparing the plurality of PTSEs representing a network configuration corresponding to the virtual network to be simulated, wherein the following input parameters are utilized: Peer Group ATM prefix, number of nodes in the virtual network, number of links per node in the virtual network, base PNNI level in the virtual network and first suffix used for constructing a node""s ATM address and creating an injection output file from the pluratity of PTSEs.
The step of injecting comprises the steps of reading the plurality of PTSEs into the node under test, parsing the plurality of PTSEs and building a plurality of corresponding binary PTSEs therefrom, processing the plurality of binary PTSEs utilizing software routines within the node under test, inserting PTSE based data into a topology database maintained within the node under test and modifying local PTSE generation so as to generate a PTSE describing a simulated link from the node under test to a node in the virtual portion of the network.
The method further comprises the step of generating a plurality of PTSEs for each desired level of hierarchy. The step of injecting comprises the step of utilizing a local PTSE generation process within one of the node under test in combination with special instruction operative to indicate the presence of a simulated virtual network to the node under test.
There is also provided in accordance with the present invention, in a Private Network to Network Interface (PNNI) based Asynchronous Transfer Mode (ATM) network, a method of simulating a virtual ATM network coupled to a real portion consisting of a plurality of real nodes, the method comprising the steps of generating a plurality of PNNI Topology State Elements (PTSEs) representing a combination of network elements that function to form the virtual network, injecting the plurality of PTSEs into one of the real nodes designated the node under test, the node under test being part of a real portion of the ATM network which, in combination with the virtual portion, make up the ATM network being tested and forming a peer group consisting of a plurality of real nodes making up the real portion and a plurality of logical nodes making up a virtual portion of the peer group, one or more real nodes in the real portion connected to one or more logical nodes in the virtual portion via one or more virtual links, wherein at least one virtual node functions as a border node and at least one virtual node functions as peer group leader of the peer group.